#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;


/*
给定一个字符串str，只由`'X'`和`'.'` 两种字符构成：`'X'`表示墙，不能放灯，也不需要点亮，`'.'`表示居民点，可以放灯，需要点亮，
如果灯放在i位置，可以让i-1，i，i+1三个位置被点亮，返回如果点亮str中**所有需要点亮的位置至少需要几盏灯
*/
int minLight(string str)
{
	int n = str.size();
	int lights = 0;//需要点灯的数量
	int i = 0;
	while(i < n)
	{
		if (str[i] == 'X') //当前位置是墙=>直接往后走
		{
			i = i + 1;
		}
		else //当前i位置是居民点
		{
			lights++;
			if (i + 1  ==  n)  //防止下面越界
				break;

			//如果i+1位置也是居民点，那么就在i+1位置放灯，那么i和i+1,i+2位置都能被点亮，而不用管i+2位置是什么
			//然后去i+3位置考察
			if (str[i + 1] == '.') 
			{
				i = i + 3;
			} 
			else //i+1位置是墙=>那么就在i位置放灯，然后去i+2位置考察
			{
				i = i + 2;
			}
		}
	}
	return lights;
}

//#include<vector>
//const int N = 10010;
//int preSum[N]; //前缀和数组
//
////生成前缀和数组
//void CreatePre(vector<int>& v)
//{
//	preSum[0] = v[0];
//	int n = v.size();
//	for (int i = 1; i < n; i++)
//	{
//		preSum[i] = preSum[i - 1] + v[i];
//	}
//}
////求数组v在[L,R]范围上的累加和
//int RangeSum(vector<int>& v, int L, int R)
//{
//	return L == 0 ? preSum[R] : preSum[R] - preSum[L - 1];
//}
//int main()
//{
//
//	return 0;
//}

//void move(char start, char end)
//{
//	printf("move:%c->%c\n", start, end);
//}
//
////pos1:起始位置    pos2:中转位置    pos3:目标位置  n:盘子数量 
//void Hanoi(char pos1, char pos2, char pos3,int n)
//{
//	if (n == 1)
//	{
//		move(pos1, pos3);
//		return;
//	}
//
//	Hanoi(pos1, pos3, pos2, n - 1);
//	move(pos1, pos3);
//	Hanoi(pos2, pos1, pos3, n - 1);
//}
//
//int main()
//{
//	Hanoi('A', 'B', 'C', 3);
//	return 0;
//}



//求字符串的子序列
//void process(string str, int index, string path,vector<string>& ans)
//{
//	if (index == str.size())
//	{
//		ans.push_back(path);
//		return;
//	}
//	process(str, index + 1, path + str[index], ans);//要当前index位置的字符,然后去index+1位置做选择
//	process(str, index + 1, path, ans); //不要当前index位置的字符,去index+1位置做选择
//}
//
//int main()
//{
//	string str = "abcaa";
//	vector<string> ans;
//	int index = 0;
//	string tmp;
//	process(str, index, tmp, ans);
//	for (auto& str : ans)
//		cout << str << endl;
//	cout << ans.size() << endl;
//	return 0;
//}




